`
https://leetcode.cn/problems/ugly-number-iii/
`

/**
 * @param {number} n
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */
var nthUglyNumber = function (n, a, b, c) {
  // 题目说本题结果在 [1, 2 * 10^9] 范围内，
  // 所以就按照这个范围初始化两端都闭的搜索区间
  let left = 1, right = 2 * 10 ** 9;
  // 搜索左侧边界的二分搜索
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (f(mid, a, b, c) < n) {
      // [1..mid] 中符合条件的元素个数不足 n，所以目标在右半边
      left = mid + 1;
    } else {
      // [1..mid] 中符合条件的元素个数大于 n，所以目标在左半边
      right = mid - 1;
    }
  }
  return left;
};

// 计算最大公因数（辗转相除/欧几里得算法）
var gcd = function (a, b) {
  if (a < b) {
    // 保证 a > b
    return gcd(b, a);
  }
  if (b === 0) {
    return a;
  }
  return gcd(b, a % b);
};

// 最小公倍数
var lcm = function (a, b) {
  // 最小公倍数就是乘积除以最大公因数
  return a * b / gcd(a, b);
};

// 计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字
var f = function (num, a, b, c) {
  const setA = Math.floor(num / a), setB = Math.floor(num / b), setC = Math.floor(num / c);
  const setAB = Math.floor(num / lcm(a, b));
  const setAC = Math.floor(num / lcm(a, c));
  const setBC = Math.floor(num / lcm(b, c));
  const setABC = Math.floor(num / lcm(lcm(a, b), c));
  // 集合论定理：A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
  return setA + setB + setC - setAB - setAC - setBC + setABC;
};